home *** CD-ROM | disk | FTP | other *** search
/ OpenGL Superbible (2nd Edition) / OpenGL SuperBible e2.iso / tools / GLUT-3.7 / PROGS / ADVANCED / RTS.C < prev    next >
Encoding:
C/C++ Source or Header  |  1998-08-12  |  57.0 KB  |  2,156 lines
  1.  
  2. /* Copyright (c) Mark J. Kilgard, 1997, 1998. */
  3.  
  4. /* This program is freely distributable without licensing fees and is
  5.    provided without guarantee or warrantee expressed or implied.  This
  6.    program is -not- in the public domain. */
  7.  
  8. /* Real-time Shadowing library, Version 0.96 */
  9.  
  10. /* XXX This is library is not fully implemented yet, but still quite
  11.    functional. */
  12.  
  13. /* XXX This code _does_ assume that you that your realloc can realloc NULL
  14.    (as specified by ANSI C).  You also should have the 1.2 version of the
  15.    OpenGL Utility (GLU) library.  SGI users need IRIX 6.2 (or higher) or IRIX 
  16.    5.3 with patch 1449 installed. */
  17.  
  18. /* This code will use multiple CPUs if available in its SGI version
  19.    using IRIX's Shared Parallel Arena facility.  The generation of
  20.    silhouettes with the GLU 1.2 tessellator is farmed out to a gang for
  21.    tessellation threads. */
  22.  
  23. /* This code will use Win32's multithreading and multiple CPUs if
  24.    available when compiled with the Visual C++ "/MT" option.  Just
  25.    like with the IRIX multiprocessor support, the generation of
  26.    silhouettes with the GLU 1.2 tessellator is farmed out to a gang
  27.    of tessellation threads. -mjk July 28, 1998. */
  28.  
  29. /* Please do not naively assume that enabling the multiprocessor
  30.    code will make rts-based programs run any faster if you do not
  31.    have multiple CPUs.  Indeed, the extra thread overhead will in
  32.    fact likely make the program slightly slower. */
  33.  
  34. #ifdef __sgi
  35. # define MP
  36. #endif
  37.  
  38. #ifdef _WIN32
  39. # ifdef _MT  /* If Visual C++ "/MT" compiler switch specified. */
  40. #  define MP
  41. # endif
  42. #endif
  43.  
  44. #define NDEBUG  /* No assertions for best performance. */
  45.  
  46. #include <assert.h>
  47. #include <stdlib.h>
  48. #include <string.h>
  49. #include <math.h>
  50. #include <stdio.h>
  51. #ifdef MP
  52. # ifdef __sgi
  53. #  include <unistd.h>
  54. #  include <sys/prctl.h>
  55. #  include <ulocks.h>
  56. #  include <signal.h>
  57. #  include <sys/sysmp.h>
  58. # endif
  59. # ifdef _WIN32
  60. #  include <windows.h>
  61. #  include <process.h>
  62. # endif
  63. #endif
  64.  
  65. #include "rtshadow.h"
  66.  
  67. /* The "real time shadows" (RTS) library code requires the GLU 1.2
  68.    polygon tessellator's boundary return capability to work. */
  69. #ifdef GLU_VERSION_1_2
  70.  
  71. /* Win32 calling conventions. */
  72. #ifndef CALLBACK
  73. #define CALLBACK
  74. #endif
  75.  
  76. /* Some <math.h> files do not define M_PI... */
  77. #ifndef M_PI
  78. #define M_PI 3.14159265358979323846
  79. #endif
  80.  
  81. /* For testing... */
  82. #if 0
  83. #undef GL_VERSION_1_1
  84. #undef GL_EXT_vertex_array
  85. #endif
  86.  
  87. #if defined(GL_VERSION_1_1) || defined(GL_EXT_vertex_array)
  88. static int hasVertexArray = 0;
  89. #else
  90. static const int hasVertexArray = 0;
  91. #endif
  92.  
  93. #ifdef GL_EXT_blend_subtract
  94. static int hasBlendSubtract = 0;
  95. #else
  96. static const int hasBlendSubtract = 0;
  97. #endif
  98.  
  99. /* Coordinates. */
  100. enum {
  101.   X, Y, Z
  102. };
  103.  
  104. struct VertexHolder2D {
  105.   struct VertexHolder2D *next;
  106.   GLfloat v[2];
  107. };
  108.  
  109. struct VertexHolder3D {
  110.   struct VertexHolder3D *next;
  111.   GLfloat v[3];
  112. };
  113.  
  114. #ifndef MP
  115.  
  116. # define NUM_CONTEXTS 1
  117. # define MP_ASSERT(assertion)
  118.  
  119. # define ARENA_VARIABLE(arena)
  120. # define SEMA_VARIABLE(sema)
  121. # define LOCK_VARIABLE(lock)
  122. # define THREAD_VARIABLE(thread)
  123. # define INITSEMA(arena)
  124. # define WAIT(sema)
  125. # define SIGNAL(sema)
  126. # define INITLOCK(arena)
  127. # define LOCK(lock)
  128. # define UNLOCK(lock)
  129. # define PRIVATE_MALLOC(size)        malloc(size)
  130. # define PRIVATE_FREE(ptr)           free(ptr)
  131. # define PRIVATE_REALLOC(ptr, size)  realloc(ptr, size)
  132. # define SHARED_MALLOC(size)         malloc(size)
  133. # define SHARED_FREE(ptr)            free(ptr)
  134. # define SHARED_REALLOC(ptr, size)   realloc(ptr, size)
  135.  
  136. #else
  137.  
  138. # define NUM_CONTEXTS 4
  139. # define MP_ASSERT(assertion)        assert(assertion)
  140.  
  141. # ifdef __sgi
  142.  
  143. #  define ARENA_VARIABLE(arena)      usptr_t *arena;
  144. #  define SEMA_VARIABLE(sema)        usema_t *sema;
  145. #  define LOCK_VARIABLE(lock)        ulock_t lock;
  146. #  define THREAD_VARIABLE(thread)    pid_t thread;
  147.  
  148. #  define INITSEMA(arena, value)     usnewsema(arena, value)
  149. #  define WAIT(sema)                 uspsema(sema)
  150. #  define SIGNAL(sema)               usvsema(sema)
  151. #  define SAMPLE(sema)               ustestsema(sema)
  152.  
  153. #  define INITLOCK(arena)            usnewlock(arena)
  154. #  define LOCK(lock)                 ussetlock(lock)
  155. #  define UNLOCK(lock)               usunsetlock(lock)
  156.  
  157. #  define PRIVATE_MALLOC(size)       malloc(size)
  158. #  define PRIVATE_FREE(ptr)          free(ptr)
  159. #  define PRIVATE_REALLOC(ptr, size) realloc(ptr, size)
  160.  
  161. #  define SHARED_MALLOC(size)        usmalloc(size, arena)
  162. #  define SHARED_FREE(ptr)           usfree(ptr, arena)
  163. #  define SHARED_REALLOC(ptr, size)  usrealloc(ptr, size, arena)
  164.  
  165. # endif  /* __sgi */
  166.  
  167. # ifdef _WIN32
  168.  
  169. #  define ARENA_VARIABLE(arena)      HANDLE arena;
  170. #  define SEMA_VARIABLE(sema)        HANDLE sema;
  171. #  define LOCK_VARIABLE(lock)        HANDLE lock;
  172. #  define THREAD_VARIABLE(thread)    HANDLE thread;
  173.  
  174. #  define INITSEMA(arena, value)     CreateSemaphore(NULL, value, NUM_CONTEXTS, NULL)
  175. #  define WAIT(sema)                 WaitForSingleObject(sema, INFINITE)
  176. #  define SIGNAL(sema)               ReleaseSemaphore(sema, 1, NULL)
  177.  
  178.    /* Does Win32 have something cheaper than a mutex for locking? */
  179. #  define INITLOCK(arena)            CreateMutex(NULL, FALSE, NULL)
  180. #  define LOCK(lock)                 WaitForSingleObject(lock, INFINITE)
  181. #  define UNLOCK(lock)               ReleaseMutex(lock)
  182.  
  183. #  define PRIVATE_MALLOC(size)       malloc(size)
  184. #  define PRIVATE_FREE(ptr)          free(ptr)
  185. #  define PRIVATE_REALLOC(ptr, size) realloc(ptr, size)
  186.  
  187. #  define SHARED_MALLOC(size)        malloc(size)
  188. #  define SHARED_FREE(ptr)           free(ptr)
  189. #  define SHARED_REALLOC(ptr, size)  realloc(ptr, size)
  190.  
  191. # endif  /* _WIN32 */
  192.  
  193. typedef enum {
  194.   CS_UNUSED, CS_CAPTURING, CS_QUEUED, CS_GENERATING
  195. } ContextState;
  196.  
  197. #endif
  198.  
  199. typedef struct ShadowVolumeState ShadowVolumeState;
  200.  
  201. typedef struct TessellationContext {
  202. #ifdef MP
  203.   ContextState state;
  204. #endif
  205.   RTSscene *scene;
  206.   RTSlight *light;
  207.   RTSobject *object;
  208.   ShadowVolumeState *svs;
  209.  
  210.   GLUtesselator *tess;
  211.  
  212.   /* For managing memory allocated by the GLU tessellator's
  213.      combine callback. */
  214.   GLfloat *combineList;
  215.   int combineListSize;
  216.   int combineNext;
  217.   struct VertexHolder2D *excessList2D;
  218.  
  219.   int saveFirst;
  220.   GLfloat *firstVertex;
  221.  
  222.   GLfloat *feedbackBuffer;
  223.   int feedbackBufferSize;
  224.   int feedbackBufferReturned;
  225.  
  226.   GLfloat shadowProjectionDistance;
  227.   GLfloat extentScale;
  228.  
  229.   int nextVertex;
  230.   int *header;
  231.   struct VertexHolder3D *excessList3D;
  232. } TessellationContext;
  233.  
  234. const float uniquePassThroughValue = 34567.0;
  235.  
  236. #define SmallerOf(a,b) ((a) < (b) ? (a) : (b))
  237.  
  238. ARENA_VARIABLE(arena)
  239. SEMA_VARIABLE(contextAvailable)
  240. LOCK_VARIABLE(accessQueue)
  241. SEMA_VARIABLE(silhouetteNeedsGeneration)
  242.  
  243. static TessellationContext *context[NUM_CONTEXTS];
  244.  
  245. struct RTSscene {
  246.   GLfloat eyePos[3];
  247.   GLbitfield usableStencilBits;
  248.   int numStencilBits;
  249.   char bitList[32];
  250.   void (*renderSceneFunc) (GLenum castingLight, void *sceneData, RTSscene * scene);
  251.   void *sceneData;
  252.  
  253.   SEMA_VARIABLE(silhouetteGenerationDone)
  254.   THREAD_VARIABLE(*workerPids)
  255. #ifdef MP
  256.   ShadowVolumeState *waitingForSVS;
  257. #endif
  258.  
  259.   GLfloat viewScale;
  260.   GLint stencilBits;
  261.   int stencilValidateNeeded;
  262.  
  263.   GLfloat sceneAmbient[4];
  264.  
  265.   int lightListSize;
  266.   RTSlight **lightList;
  267.  
  268.   GLboolean stencilRenderingInvariantHack;
  269. };
  270.  
  271. struct ShadowVolumeState {
  272.   int lightSernum;
  273.   int objectSernum;
  274. #ifdef MP
  275.   int generationDone;
  276. #endif
  277.  
  278.   int silhouetteSize;
  279.   GLfloat *silhouette;
  280.  
  281.   GLfloat angle;
  282.   GLfloat axis[3];
  283.  
  284.   GLfloat topScale;
  285. };
  286.  
  287. struct RTSlight {
  288.   int refcnt;
  289.   int sernum;
  290.  
  291.   GLenum glLight;
  292.   GLfloat lightPos[3];
  293.   GLfloat radius;
  294.  
  295.   int state;
  296.  
  297.   int sceneListSize;
  298.   RTSscene **sceneList;
  299.  
  300.   int objectListSize;
  301.   RTSobject **objectList;
  302.   ShadowVolumeState *shadowVolumeList;
  303. };
  304.  
  305. struct RTSobject {
  306.   int refcnt;
  307.   int sernum;
  308.  
  309.   GLfloat objectPos[3];
  310.   GLfloat maxRadius;
  311.   void (*renderObject) (void *objectData);
  312.   void *objectData;
  313.  
  314.   int feedbackBufferSizeGuess;
  315.  
  316.   int state;
  317.  
  318.   int lightListSize;
  319.   RTSlight **lightList;
  320. };
  321.  
  322. #if defined(GL_VERSION_1_1)
  323. static int
  324. supportsOneDotOne(void)
  325. {
  326.   const char *version;
  327.   int major, minor;
  328.  
  329.   version = (char *) glGetString(GL_VERSION);
  330.   if (sscanf(version, "%d.%d", &major, &minor) == 2)
  331.     return major >= 1 && minor >= 1;
  332.   return 0;             /* OpenGL version string malformed! */
  333. }
  334. #endif
  335.  
  336. static int
  337. extensionSupported(const char *extension)
  338. {
  339.   static const GLubyte *extensions = NULL;
  340.   const GLubyte *start;
  341.   GLubyte *where, *terminator;
  342.  
  343.   /* Extension names should not have spaces. */
  344.   where = (GLubyte *) strchr(extension, ' ');
  345.   if (where || *extension == '\0')
  346.     return 0;
  347.  
  348.   if (!extensions)
  349.     extensions = glGetString(GL_EXTENSIONS);
  350.   /* It takes a bit of care to be fool-proof about parsing the OpenGL
  351.      extensions string.  Don't be fooled by sub-strings,  etc. */
  352.   start = extensions;
  353.   for (;;) {
  354.     where = (GLubyte *) strstr((const char *) start, extension);
  355.     if (!where)
  356.       break;
  357.     terminator = where + strlen(extension);
  358.     if (where == start || *(where - 1) == ' ') {
  359.       if (*terminator == ' ' || *terminator == '\0') {
  360.         return 1;
  361.       }
  362.     }
  363.     start = terminator;
  364.   }
  365.   return 0;
  366. }
  367.  
  368. static GLfloat *
  369. nextVertexHolder3D(TessellationContext * context)
  370. {
  371.   struct VertexHolder3D *holder;
  372.   ShadowVolumeState *svs;
  373.   GLfloat *newHolder;
  374.  
  375.   svs = context->svs;
  376.   if (context->nextVertex >= svs->silhouetteSize) {
  377.     holder = (struct VertexHolder3D *) PRIVATE_MALLOC(sizeof(struct VertexHolder3D));
  378.     if (holder == NULL) {
  379.       printf("holder alloc problem\n");
  380.     }
  381.     holder->next = context->excessList3D;
  382.     context->excessList3D = holder;
  383.     newHolder = holder->v;
  384.   } else {
  385.     newHolder = &svs->silhouette[context->nextVertex * 3];
  386.   }
  387.   context->nextVertex++;
  388.   return newHolder;
  389. }
  390.  
  391. /* ARGSUSED */
  392. static void CALLBACK
  393. begin(GLenum type, void *polyData)
  394. {
  395.   TessellationContext *context = polyData;
  396.   GLfloat *newHolder;
  397.  
  398.   assert(type == GL_LINE_LOOP);
  399.   context->saveFirst = 1;
  400.  
  401.   context->header = (int *) nextVertexHolder3D(context);
  402.   context->header[0] = context->nextVertex;
  403.   context->header[1] = 0xdeadbabe;  /* Aid assertion testing. */
  404.   context->header[2] = 0xdeadbeef;  /* Non-termintor token. */
  405.  
  406.   newHolder = nextVertexHolder3D(context);
  407.   newHolder[X] = 0.0;
  408.   newHolder[Y] = 0.0;
  409.   newHolder[Z] = 0.0;
  410. }
  411.  
  412. static void CALLBACK
  413. vertex(void *data, void *polyData)
  414. {
  415.   TessellationContext *context = polyData;
  416.   GLfloat *v = data;
  417.   GLfloat *newHolder;
  418.  
  419.   newHolder = nextVertexHolder3D(context);
  420.   newHolder[X] = context->extentScale * v[X];
  421.   newHolder[Y] = context->extentScale * v[Y];
  422.   newHolder[Z] = context->shadowProjectionDistance;
  423.   if (context->saveFirst) {
  424.     context->firstVertex = newHolder;
  425.     context->saveFirst = 0;
  426.   }
  427. }
  428.  
  429. static void CALLBACK
  430. end(void *polyData)
  431. {
  432.   TessellationContext *context = polyData;
  433.   GLfloat *newHolder;
  434.  
  435.   newHolder = nextVertexHolder3D(context);
  436.   newHolder[X] = context->firstVertex[X];
  437.   newHolder[Y] = context->firstVertex[Y];
  438.   newHolder[Z] = context->firstVertex[Z];
  439.   assert(context->firstVertex[Z] == context->shadowProjectionDistance);
  440.  
  441.   assert(context->header[1] == 0xdeadbabe);
  442.   assert(context->header[2] == 0xdeadbeef);
  443.   context->header[1] = context->nextVertex - context->header[0];
  444. }
  445.  
  446. static void
  447. freeExcessList(TessellationContext * context)
  448. {
  449.   struct VertexHolder2D *holder, *next;
  450.  
  451.   holder = context->excessList2D;
  452.   while (holder) {
  453.     next = holder->next;
  454.     PRIVATE_FREE(holder);
  455.     holder = next;
  456.   }
  457.   context->excessList2D = NULL;
  458. }
  459.  
  460. /* The GLU tessellator's combine callback is called to create a
  461.    new vertex when tessellation detects an intersection or wishes
  462.    to merge features.
  463.  
  464.    The memory for the new vertex must be allocated by the GLU
  465.    tessellator caller.  The caller is also responsible for this
  466.    memory's deletion.  The combineList is an array for the memory
  467.    for these combined vertices.  The array is of size combineListSize.
  468.    combineNext decides how many vertices are in use on the combineList.
  469.  
  470.    The combineList is of finite size.  When this list is exhausted,
  471.    individual vertex memory is allocated via malloc in a linked list.
  472.    This is the excessList2D linked list.  After tessellation, the
  473.    combineList will be expanded by how many vertices had to be
  474.    added to the excessList2D list.  The idea is that next time the
  475.    shadow volume tessellation is done, the combineList should
  476.    hopefully be large enough.
  477.  
  478. /* ARGSUSED1 */
  479. static void CALLBACK
  480. combine(GLdouble coords[3], void *d[4], GLfloat w[4],
  481.   void **dataOut, void *polyData)
  482. {
  483.   TessellationContext *context = polyData;
  484.   struct VertexHolder2D *holder;
  485.   GLfloat *newHolder;
  486.  
  487.   if (context->combineNext >= context->combineListSize) {
  488.     holder = (struct VertexHolder2D *) PRIVATE_MALLOC(sizeof(struct VertexHolder2D));
  489.     if (holder == NULL) {
  490.       printf("got no holder alloc\n");
  491.     }
  492.     holder->next = context->excessList2D;
  493.     context->excessList2D = holder;
  494.     newHolder = holder->v;
  495.   } else {
  496.     newHolder = &context->combineList[context->combineNext * 2];
  497.   }
  498.  
  499.   newHolder[0] = (GLfloat) coords[0];
  500.   newHolder[1] = (GLfloat) coords[1];
  501.   *dataOut = newHolder;
  502.  
  503.   context->combineNext++;
  504. }
  505.  
  506. static void CALLBACK
  507. error(GLenum errno)
  508. {
  509.   fprintf(stderr, "ERROR: %s\n", gluErrorString(errno));
  510. }
  511.  
  512. #ifdef DEBUG
  513.  
  514. /* These verify routines are useful for asserting the sanity of
  515.    the silhouette data structures. */
  516.  
  517. static void
  518. verifySilhouette(ShadowVolumeState * svs)
  519. {
  520.   int *infoPtr = (int *) svs->silhouette;
  521.   int *info = infoPtr;
  522.   int fan;
  523.  
  524.   if (info[0] == 0) {
  525.     printf("2 ZERO\n");
  526.   }
  527.   if (info ==0) {
  528.     printf("ZERO\n");
  529.   }
  530.   fan = 0;
  531.   for (;;) {
  532.     if(info[2] == 0xdeadbeef || info[2] == 0xcafecafe) {
  533.       if (info[2] == 0xcafecafe) {
  534.         return;
  535.       }
  536.       info += ((1 + info[1]) * 3);
  537.       fan++;
  538.     } else {
  539.       printf("Corrupted silhouette! (svs=0x%x, silhouette=0x%x, fan=%d)\n",
  540.         svs, svs->silhouette, fan);
  541.       abort();
  542.     }
  543.   }
  544. }
  545.  
  546. static void
  547. verifySilhouettesOfScene(RTSscene *scene)
  548. {
  549.   int i, obj;
  550.   RTSlight *light;
  551.  
  552.   for (i = 0; i < scene->lightListSize; i++) {
  553.     light = scene->lightList[i];
  554.     if (light) {
  555.       for (obj = 0; obj < light->objectListSize; obj++) {
  556.         ShadowVolumeState *svs;
  557.  
  558.         svs = &light->shadowVolumeList[obj];
  559.     if (svs && svs->generationDone) {
  560.       verifySilhouette(svs);
  561.     }
  562.       }
  563.     }
  564.   }
  565. }
  566.  
  567. #endif
  568.  
  569. static void
  570. generateSilhouette(TessellationContext * context)
  571. {
  572.   ShadowVolumeState * svs;
  573.   GLfloat *start, *end, *loc;
  574.   GLfloat *eyeLoc;
  575.   GLdouble v[3];
  576.   int token, nvertices, i;
  577.   GLfloat passThroughToken;
  578.   int watchingForEyePos;
  579.   struct VertexHolder3D *holder, *next;
  580.  
  581.   assert(context->excessList2D == NULL);
  582.   assert(context->excessList3D == NULL);
  583.  
  584.   svs = context->svs;
  585.  
  586.   context->nextVertex = 0;
  587.  
  588.   watchingForEyePos = 0;
  589.   eyeLoc = NULL;
  590.  
  591.   gluTessBeginPolygon(context->tess, context);
  592.   start = context->feedbackBuffer;
  593.   end = start + context->feedbackBufferReturned;
  594.   for (loc = start; loc < end;) {
  595.     token = *loc;
  596.     loc++;
  597.     switch (token) {
  598.     case GL_POLYGON_TOKEN:
  599.       nvertices = *loc;
  600.       loc++;
  601.       assert(nvertices >= 3);
  602.       gluTessBeginContour(context->tess);
  603.       for (i = 0; i < nvertices; i++) {
  604.         v[0] = loc[0];
  605.         v[1] = loc[1];
  606.         v[2] = 0.0;
  607.         gluTessVertex(context->tess, v, loc);
  608.         loc += 2;
  609.       }
  610.       gluTessEndContour(context->tess);
  611.       break;
  612.     case GL_PASS_THROUGH_TOKEN:
  613.       passThroughToken = *loc;
  614.       if (passThroughToken == uniquePassThroughValue) {
  615.         watchingForEyePos = !watchingForEyePos;
  616.       } else {
  617.         /* Ignore everything else. */
  618.         fprintf(stderr, "WARNING: Unexpected feedback token 0x%x (%d).\n",
  619.           token, token);
  620.       }
  621.       loc++;
  622.       break;
  623.     case GL_POINT_TOKEN:
  624.       if (watchingForEyePos) {
  625.         fprintf(stderr,
  626.           "WARNING: Eye point possibly within the shadow volume.\n");
  627.         fprintf(stderr,
  628.           "         Program should be improved to handle this.\n");
  629.         /* XXX Write code to handle this case.  You would need to determine
  630.            if the point was instead any of the returned boundary polyons.
  631.            Once you found that you were really in the clipping volume, then I
  632.            haven't quite thought about what you do. */
  633.         eyeLoc = loc;
  634.         watchingForEyePos = 0;
  635.       } else {
  636.         /* Ignore everything else. */
  637.         fprintf(stderr, "WARNING: Unexpected feedback token 0x%x (%d).\n",
  638.           token, token);
  639.       }
  640.       loc += 2;
  641.       break;
  642.     default:
  643.       /* Ignore everything else. */
  644.       fprintf(stderr, "WARING: Unexpected feedback token 0x%x (%d).\n",
  645.         token, token);
  646.     }
  647.   }
  648.   gluTessEndPolygon(context->tess);
  649.  
  650.   /* Free any memory that got allocated due to the combine callback during
  651.      tessellation and then enlarge the combineList so we hopefully don't need
  652.      the combine list next time. */
  653.   if (context->combineNext > context->combineListSize) {
  654.     freeExcessList(context);
  655.     context->combineListSize = context->combineNext;
  656.     SHARED_FREE(context->combineList);
  657.     context->combineList = SHARED_MALLOC(sizeof(GLfloat) * 2 * context->combineListSize);
  658.     if (context->combineList == NULL) {
  659.       printf("problem alloc context->combineList\n");
  660.     }
  661.   }
  662.   context->combineNext = 0;
  663.  
  664.   context->header[2] = 0xcafecafe;  /* Terminating token. */
  665.  
  666.   if (context->excessList3D) {
  667. #ifndef NDEBUG
  668.     int oldSize;
  669.  
  670.     oldSize = svs->silhouetteSize;
  671. #endif
  672.     assert(context->nextVertex > svs->silhouetteSize);
  673.     svs->silhouetteSize = context->nextVertex;
  674.     svs->silhouette = SHARED_REALLOC(svs->silhouette,
  675.       svs->silhouetteSize * sizeof(GLfloat) * 3);
  676.     if (svs->silhouette == NULL) {
  677.       fprintf(stderr, "libRTS: generateSilhouette: out of memory\n");
  678.       abort();
  679.     }
  680.     holder = context->excessList3D;
  681.     while (holder) {
  682.       context->nextVertex--;
  683.       svs->silhouette[context->nextVertex * 3] = holder->v[0];
  684.       svs->silhouette[context->nextVertex * 3 + 1] = holder->v[1];
  685.       svs->silhouette[context->nextVertex * 3 + 2] = holder->v[2];
  686.       next = holder->next;
  687.       PRIVATE_FREE(holder);
  688.       holder = next;
  689.     }
  690.     assert(context->nextVertex == oldSize);
  691.     context->excessList3D = NULL;
  692.   }
  693.  
  694.   /* Validate shadow volume state's serial numbers. */
  695.   svs->lightSernum = context->light->sernum;
  696.   svs->objectSernum = context->object->sernum;
  697. }
  698.  
  699. static int
  700. listBits(GLbitfield usableStencilBits, char bitList[32])
  701. {
  702.   int num = 0, bit = 0;
  703.  
  704.   while (usableStencilBits) {
  705.     if (usableStencilBits & 0x1) {
  706.       bitList[num] = bit;
  707.       num++;
  708.     }
  709.     bit++;
  710.     usableStencilBits >>= 1;
  711.   }
  712.   return num;
  713. }
  714.  
  715. /* Three element vector dot product. */
  716. static GLfloat
  717. vdot(const GLfloat * v1, const GLfloat * v2)
  718. {
  719.   return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2];
  720. }
  721.  
  722. /* Three element vector cross product. */
  723. static void
  724. vcross(const GLfloat * v1, const GLfloat * v2, GLfloat * cross)
  725. {
  726.   assert(v1 != cross && v2 != cross);
  727.   cross[0] = (v1[1] * v2[2]) - (v1[2] * v2[1]);
  728.   cross[1] = (v1[2] * v2[0]) - (v1[0] * v2[2]);
  729.   cross[2] = (v1[0] * v2[1]) - (v1[1] * v2[0]);
  730. }
  731.  
  732. static GLfloat
  733. getViewScale(RTSscene * scene)
  734. {
  735.   if (scene->viewScale == 0.0) {
  736.     GLfloat maxViewSize[2];
  737.  
  738.     glGetFloatv(GL_MAX_VIEWPORT_DIMS, maxViewSize);
  739.     scene->viewScale = SmallerOf(maxViewSize[0], maxViewSize[1]) / 2.0;
  740.  
  741.     /* Other stuff piggy backs on viewScale to ensure initialization. */
  742.  
  743.     glGetIntegerv(GL_STENCIL_BITS, &scene->stencilBits);
  744.  
  745. #if defined(GL_VERSION_1_1)
  746.     hasVertexArray = supportsOneDotOne();
  747. #elif defined(GL_EXT_vertex_array)
  748.     hasVertexArray = extensionSupported("GL_EXT_vertex_array");
  749. #endif
  750.  
  751. #ifdef GL_EXT_blend_subtract
  752.     hasBlendSubtract = extensionSupported("GL_EXT_blend_subtract");
  753.  
  754.     /* XXX RealityEngine workaround. */
  755.     if (!strcmp((char *) glGetString(GL_VENDOR), "SGI")) {
  756.       if (!strncmp((char *) glGetString(GL_RENDERER), "RE", 2)) {
  757.         fprintf(stderr, "WARNING: RealityEngine workaround forcing additive blending.\n");
  758.         hasBlendSubtract = 0;
  759.       }
  760.     }
  761. #endif
  762.   }
  763.   return scene->viewScale;
  764. }
  765.  
  766. static void
  767. captureLightView(RTSscene * scene, RTSlight * light, RTSobject * object,
  768.   ShadowVolumeState * svs, TessellationContext * context)
  769. {
  770.   static GLfloat unit[3] =
  771.   {0.0, 0.0, 1.0};
  772.   int feedbackBufferSizeGuess;
  773.   GLfloat lightDelta[3], eyeDelta[3];
  774.   GLfloat lightDistance, eyeDistance, fieldOfViewRatio, viewScale;
  775.   GLdouble fieldOfViewAngle;
  776.   GLdouble nnear, ffar;  /* Avoid x86 C keywords.  Grumble. */
  777.   GLint returned;
  778.  
  779.   MP_ASSERT(context->state == CS_CAPTURING);
  780.   viewScale = getViewScale(scene);
  781.  
  782. #ifdef MP
  783.   svs->generationDone = 0;
  784. #endif
  785.  
  786.   glMatrixMode(GL_PROJECTION);
  787.   glPushMatrix();
  788.   glLoadIdentity();
  789.  
  790.   /* Calculate the light's distance from the object being shadowed. */
  791.   lightDelta[X] = object->objectPos[X] - light->lightPos[X];
  792.   lightDelta[Y] = object->objectPos[Y] - light->lightPos[Y];
  793.   lightDelta[Z] = object->objectPos[Z] - light->lightPos[Z];
  794.   lightDistance = (GLfloat) sqrt(lightDelta[X] * lightDelta[X] +
  795.     lightDelta[Y] * lightDelta[Y] + lightDelta[Z] * lightDelta[Z]);
  796.  
  797.   /* Determine the appropriate field of view.  We want to use as narrow a
  798.      field of view as possible to not waste resolution, but not narrower than
  799.      the object.  Add 50% extra slop. */
  800.   fieldOfViewRatio = object->maxRadius / lightDistance;
  801.   if (fieldOfViewRatio > 0.99) {
  802.     fprintf(stderr,
  803.       "WARNING: Clamping FOV to 164 degrees for determining shadow.\n");
  804.     fprintf(stderr,
  805.       "         Light distance = %g, object maxmium radius = %g\n",
  806.       lightDistance, object->maxRadius);
  807.  
  808.     /* 2*asin(0.99) ~= 164 degrees. */
  809.     fieldOfViewRatio = 0.99;
  810.   }
  811.   /* Pre-compute scaling factors for the near and far extent of the shadow
  812.      volume. */
  813.   context->extentScale = light->radius * fieldOfViewRatio / viewScale;
  814.   context->shadowProjectionDistance = light->radius;
  815.  
  816.   nnear = 0.5 * (lightDistance - object->maxRadius);
  817.   if (nnear < 0.0001) {
  818.     fprintf(stderr,
  819.       "WARNING: Clamping near clip plane to 0.0001 because light source too near.\n");
  820.     fprintf(stderr,
  821.       "         Light distance = %g, object maxmium radius = %g\n",
  822.       lightDistance, object->maxRadius);
  823.     nnear = 0.0001;
  824.   }
  825.   ffar = 2.0 * (lightDistance + object->maxRadius);
  826.  
  827.   eyeDelta[X] = scene->eyePos[X] - light->lightPos[X];
  828.   eyeDelta[Y] = scene->eyePos[Y] - light->lightPos[Y];
  829.   eyeDelta[Z] = scene->eyePos[Z] - light->lightPos[Z];
  830.   eyeDistance = 1.05 *
  831.     sqrt(eyeDelta[X] * eyeDelta[X] + eyeDelta[Y] * eyeDelta[Y]
  832.     + eyeDelta[Z] * eyeDelta[Z]);
  833.   if (eyeDistance > ffar) {
  834.     ffar = eyeDistance;
  835.   }
  836.   fieldOfViewAngle = 2.0 * asin(fieldOfViewRatio) * 180 / M_PI;
  837.   gluPerspective(fieldOfViewAngle, 1.0, nnear, ffar);
  838.  
  839.   glMatrixMode(GL_MODELVIEW);
  840.   glPushMatrix();
  841.   glLoadIdentity();
  842.   /* XXX Look up vector needs adjusting. */
  843.   gluLookAt(light->lightPos[X], light->lightPos[Y], light->lightPos[Z],
  844.     object->objectPos[X], object->objectPos[Y], object->objectPos[Z],
  845.     0.0, 1.0, 0.0);     /* up is in positive Y direction */
  846.  
  847.   glPushAttrib(GL_VIEWPORT_BIT);
  848.   glViewport(-viewScale, -viewScale, 2 * viewScale, 2 * viewScale);
  849.  
  850.   feedbackBufferSizeGuess = object->feedbackBufferSizeGuess;
  851.  
  852. doFeedback:
  853.  
  854.   if (feedbackBufferSizeGuess > context->feedbackBufferSize) {
  855.     context->feedbackBufferSize = feedbackBufferSizeGuess;
  856.     object->feedbackBufferSizeGuess = feedbackBufferSizeGuess;
  857.  
  858.     /* A "free & malloc" is better than a "realloc" below because we
  859.        do not care for the previous buffer contents to be preserved. */
  860.     /* XXX Add 32 words of slop (an extra cache line) to end for buggy
  861.        hardware that uses DMA to return feedback results but that sometimes
  862.        overrun the buffer.  Yuck. */
  863.     SHARED_FREE(context->feedbackBuffer);
  864.     context->feedbackBuffer = (GLfloat *)
  865.       SHARED_MALLOC(context->feedbackBufferSize * sizeof(GLfloat) + 32 * 4);
  866.     if (context->feedbackBuffer == NULL) {
  867.       fprintf(stderr, "libRTS: captureLightView: out of memory\n");
  868.       abort();
  869.     }
  870.   }
  871.   glFeedbackBuffer(context->feedbackBufferSize,
  872.     GL_2D, context->feedbackBuffer);
  873.  
  874.   (void) glRenderMode(GL_FEEDBACK);
  875.  
  876.   /* Render the eye position.  The eye position is "bracketed" by unique pass
  877.      through tokens.  These bracketing pass through tokens let us determine if
  878.      the eye position was clipped or not.  This helps us determine whether  the
  879.      eye position is possibly within the shadow volume or not.  If the point is
  880.      clipped, the eye position is not in the shadow volume.  If the point is
  881.      not clipped, a more complicated test is necessary to determine if the eye
  882.      position is really in the shadow volume or not.  See generateSilhouette. */
  883.   glPassThrough(uniquePassThroughValue);
  884.   glBegin(GL_POINTS);
  885.   glVertex3fv(scene->eyePos);
  886.   glEnd();
  887.   glPassThrough(uniquePassThroughValue);
  888.  
  889.   (object->renderObject) (object->objectData);
  890.  
  891.   returned = glRenderMode(GL_RENDER);
  892.   assert(returned <= context->feedbackBufferSize);
  893. #if 0
  894.   if (returned == -1) {
  895. #else
  896.   /* XXX RealityEngine workaround. */
  897.   if (returned == -1 || returned == context->feedbackBufferSize) {
  898. #endif
  899.     feedbackBufferSizeGuess = context->feedbackBufferSize
  900.       + (context->feedbackBufferSize >> 1);
  901.     goto doFeedback;    /* Try again with larger feedback buffer. */
  902.   }
  903.   glMatrixMode(GL_PROJECTION);
  904.   glPopMatrix();
  905.   glMatrixMode(GL_MODELVIEW);
  906.   glPopMatrix();
  907.   glPopAttrib();        /* Restore viewport. */
  908.  
  909.   vcross(unit, lightDelta, svs->axis);
  910.   svs->angle = (GLfloat) acos(vdot(unit, lightDelta) / lightDistance) * 180.0 / M_PI;
  911.   svs->topScale = (lightDistance + object->maxRadius) / light->radius;
  912.  
  913.   context->feedbackBufferReturned = returned;
  914.  
  915.   context->scene = scene;
  916.   context->light = light;
  917.   context->object = object;
  918.   context->svs = svs;
  919. }
  920.  
  921. static TessellationContext *
  922. createTessellationContext(void)
  923. {
  924.   TessellationContext *context;
  925.   GLUtesselator *tess;
  926.  
  927.   context = (TessellationContext *) SHARED_MALLOC(sizeof(TessellationContext));
  928.   if (context == NULL) {
  929.     printf("TessellationContext alloc failed\n");
  930.     return NULL;
  931.   }
  932.   tess = gluNewTess();
  933.   if (tess == NULL) {
  934.     SHARED_FREE(context);
  935.     return NULL;
  936.   }
  937.   gluTessProperty(tess, GLU_TESS_BOUNDARY_ONLY, GL_TRUE);
  938.   gluTessProperty(tess, GLU_TESS_WINDING_RULE, GLU_TESS_WINDING_NONZERO);
  939.   gluTessCallback(tess, GLU_TESS_BEGIN_DATA, (void (CALLBACK*)()) &begin);
  940.   gluTessCallback(tess, GLU_TESS_VERTEX_DATA, (void (CALLBACK*)()) &vertex);
  941.   gluTessCallback(tess, GLU_TESS_COMBINE_DATA, (void (CALLBACK*)()) &combine);
  942.   gluTessCallback(tess, GLU_TESS_END_DATA, (void (CALLBACK*)()) &end);
  943.   gluTessCallback(tess, GLU_TESS_ERROR, error);
  944.   context->tess = tess;
  945.  
  946. #ifdef MP
  947.   context->state = CS_UNUSED;
  948. #endif
  949.   context->combineListSize = 0;
  950.   context->combineList = NULL;
  951.   context->combineNext = 0;
  952.   context->excessList2D = NULL;
  953.  
  954.   context->feedbackBufferSize = 0;
  955.   context->feedbackBuffer = NULL;
  956.  
  957.   context->excessList3D = NULL;
  958.  
  959.   return context;
  960. }
  961.  
  962. #ifdef MP
  963.  
  964. static void
  965. work(void)
  966. {
  967.   TessellationContext *workContext;
  968.   RTSscene *scene;
  969.   int i;
  970.  
  971.     WAIT(silhouetteNeedsGeneration);
  972.  
  973.     LOCK(accessQueue);
  974.     workContext = NULL;
  975.     for (i=0; i<NUM_CONTEXTS; i++) {
  976.       if (context[i]->state == CS_QUEUED) {
  977.         workContext = context[i];
  978.     break;
  979.       }
  980.     }
  981.     assert(workContext);
  982.     workContext->state = CS_GENERATING;
  983.     UNLOCK(accessQueue);
  984.  
  985.     generateSilhouette(workContext);
  986.  
  987.     LOCK(accessQueue);
  988.     assert(workContext->state == CS_GENERATING);
  989.     workContext->state = CS_UNUSED;
  990.     workContext->svs->generationDone = 1;
  991.     scene = workContext->scene;
  992.  
  993.     /* If the main thread is sleeping on this particular
  994.        shadow volume, wake up the main thread. */
  995.     if (workContext->svs == scene->waitingForSVS) {
  996.       scene->waitingForSVS = NULL;
  997.       SIGNAL(scene->silhouetteGenerationDone);
  998.     }
  999.     UNLOCK(accessQueue);
  1000.     SIGNAL(contextAvailable);
  1001. }
  1002.  
  1003. static void
  1004. waitForSilhouetteGenerationDone(RTSscene * scene, ShadowVolumeState *svs)
  1005. {
  1006.   LOCK(accessQueue);
  1007.  
  1008.   if (svs->generationDone == 0) {
  1009.     scene->waitingForSVS = svs;
  1010.     UNLOCK(accessQueue);
  1011.     WAIT(scene->silhouetteGenerationDone);
  1012.     assert(svs->generationDone);
  1013.   } else {
  1014.     UNLOCK(accessQueue);
  1015.   }
  1016. }
  1017.  
  1018. #ifdef __sgi
  1019.  
  1020. static void
  1021. worker(void)
  1022. {
  1023.   signal(SIGHUP, SIG_DFL);
  1024.   prctl(PR_TERMCHILD);
  1025.   usadd(arena);
  1026.   for (;;) {
  1027.     work();
  1028.   }
  1029. }
  1030.  
  1031. static void
  1032. setupArena(int numWorkers)
  1033. {
  1034.   static int beenhere = 0;
  1035.   int i;
  1036.   THREAD_VARIABLE(pid)
  1037.  
  1038.   if (beenhere) {
  1039.     return;
  1040.   }
  1041.   beenhere = 1;
  1042.  
  1043.   usconfig(CONF_INITUSERS, 1 + numWorkers);
  1044.   usconfig(CONF_ARENATYPE, US_SHAREDONLY);
  1045.   usconfig(CONF_INITSIZE, 1024 * 1024);
  1046.   arena = usinit("/dev/zero");
  1047.   if (arena == NULL) {
  1048.     fprintf(stderr, "libRTS: could not create arena.\n");
  1049.     exit(1);
  1050.   }
  1051.  
  1052.   for (i=0; i<NUM_CONTEXTS; i++) {
  1053.     context[i] = createTessellationContext();
  1054.   }
  1055.  
  1056.   contextAvailable = INITSEMA(arena, NUM_CONTEXTS);
  1057.   accessQueue = INITLOCK(arena);
  1058.   silhouetteNeedsGeneration = INITSEMA(arena, 0);
  1059.  
  1060.   for (i=0; i<numWorkers; i++) {
  1061.     pid = fork();
  1062.     if (pid == -1) {
  1063.       perror("fork");
  1064.       exit(1);
  1065.     }
  1066.     if (pid == 0) {
  1067.       worker();
  1068.     }
  1069.   }
  1070. }
  1071.  
  1072. #endif  /* __sgi */
  1073.  
  1074. #ifdef _WIN32
  1075.  
  1076. static void
  1077. worker(void *unused)
  1078. {
  1079.   for (;;) {
  1080.     work();
  1081.   }
  1082. }
  1083.  
  1084. static void
  1085. setupArena(int numWorkers)
  1086. {
  1087.   static int beenhere = 0;
  1088.   int i;
  1089.   unsigned long retval;
  1090.  
  1091.   if (beenhere) {
  1092.     return;
  1093.   }
  1094.   beenhere = 1;
  1095.  
  1096.   for (i=0; i<NUM_CONTEXTS; i++) {
  1097.     context[i] = createTessellationContext();
  1098.   }
  1099.  
  1100.   contextAvailable = INITSEMA(arena, NUM_CONTEXTS);
  1101.   accessQueue = INITLOCK(arena);
  1102.   silhouetteNeedsGeneration = INITSEMA(arena, 0);
  1103.  
  1104.   for (i=0; i<numWorkers; i++) {
  1105.     retval = _beginthread(worker, 0, NULL);
  1106.     if (retval == -1) {
  1107.       perror("_beginthread");
  1108.       exit(1);
  1109.     }
  1110.   }
  1111. }
  1112.  
  1113. #endif  /* _WIN32 */
  1114.  
  1115. #endif  /* MP */
  1116.  
  1117. RTSscene *
  1118. rtsCreateScene(
  1119.   GLfloat eyePos[3],
  1120.   GLbitfield usableStencilBits,
  1121.   void (*renderSceneFunc) (GLenum castingLight, void *sceneData, RTSscene * scene),
  1122.   void *sceneData)
  1123. {
  1124.   RTSscene *scene;
  1125.  
  1126. #ifdef MP
  1127. # ifdef __sgi
  1128.   int numProcessors = (int) sysmp(MP_NAPROCS);
  1129.  
  1130.   printf("numProcesasors = %d\n", numProcessors);
  1131.   setupArena(SmallerOf(4, numProcessors));
  1132. # endif
  1133. # ifdef _WIN32
  1134.   int numProcessors = 2;
  1135.  
  1136.   printf("numProcessors = %d\n", numProcessors);
  1137.   setupArena(numProcessors);
  1138. # endif
  1139. #else
  1140.   context[0] = createTessellationContext();
  1141. #endif
  1142.  
  1143.   scene = (RTSscene *) SHARED_MALLOC(sizeof(RTSscene));
  1144.   if (scene == NULL) {
  1145.     printf("rtsCreateScene alloc failed\n");
  1146.     return NULL;
  1147.   }
  1148.  
  1149. #ifdef MP
  1150.   scene->silhouetteGenerationDone = INITSEMA(arena, 0);
  1151.   scene->waitingForSVS = NULL;
  1152. #endif
  1153.  
  1154.   scene->eyePos[X] = eyePos[X];
  1155.   scene->eyePos[Y] = eyePos[Y];
  1156.   scene->eyePos[Z] = eyePos[Z];
  1157.   scene->usableStencilBits = usableStencilBits;
  1158.   scene->renderSceneFunc = renderSceneFunc;
  1159.   scene->sceneData = sceneData;
  1160.  
  1161.   scene->viewScale = 0.0;  /* 0.0 means "to be determined". */
  1162.   scene->stencilValidateNeeded = 1;
  1163.  
  1164.   scene->sceneAmbient[0] = 0.2;
  1165.   scene->sceneAmbient[1] = 0.2;
  1166.   scene->sceneAmbient[2] = 0.2;
  1167.   scene->sceneAmbient[3] = 1.0;
  1168.  
  1169.   scene->lightListSize = 0;
  1170.   scene->lightList = NULL;
  1171.  
  1172.   scene->stencilRenderingInvariantHack = GL_FALSE;
  1173.  
  1174.   return scene;
  1175. }
  1176.  
  1177. RTSlight *
  1178. rtsCreateLight(
  1179.   GLenum glLight,
  1180.   GLfloat lightPos[3],
  1181.   GLfloat radius)
  1182. {
  1183.   RTSlight *light;
  1184.  
  1185.   light = (RTSlight *) SHARED_MALLOC(sizeof(RTSlight));
  1186.   if (light == NULL) {
  1187.     printf("rtsCreateLight failed\n");
  1188.     return NULL;
  1189.   }
  1190.   light->refcnt = 1;
  1191.   light->sernum = 1;
  1192.  
  1193.   light->glLight = glLight;
  1194.   light->lightPos[X] = lightPos[X];
  1195.   light->lightPos[Y] = lightPos[Y];
  1196.   light->lightPos[Z] = lightPos[Z];
  1197.   light->radius = radius;
  1198.  
  1199.   light->state = RTS_SHINING_AND_CASTING;
  1200.  
  1201.   light->sceneListSize = 0;
  1202.   light->sceneList = NULL;
  1203.  
  1204.   light->objectListSize = 0;
  1205.   light->objectList = NULL;
  1206.   light->shadowVolumeList = NULL;
  1207.  
  1208.   return light;
  1209. }
  1210.  
  1211. RTSobject *
  1212. rtsCreateObject(
  1213.   GLfloat objectPos[3],
  1214.   GLfloat maxRadius,
  1215.   void (*renderObject) (void *objectData),
  1216.   void *objectData,
  1217.   int feedbackBufferSizeGuess)
  1218. {
  1219.   RTSobject *object;
  1220.  
  1221.   object = (RTSobject *) SHARED_MALLOC(sizeof(RTSobject));
  1222.   if (object == NULL) {
  1223.     printf("rtsCreateObject failed\n");
  1224.     return NULL;
  1225.   }
  1226.   object->refcnt = 1;
  1227.   object->sernum = 1;
  1228.  
  1229.   object->objectPos[X] = objectPos[X];
  1230.   object->objectPos[Y] = objectPos[Y];
  1231.   object->objectPos[Z] = objectPos[Z];
  1232.   object->maxRadius = maxRadius;
  1233.   object->renderObject = renderObject;
  1234.   object->objectData = objectData;
  1235.   object->feedbackBufferSizeGuess = feedbackBufferSizeGuess;
  1236. #ifdef __sgi
  1237.   /* XXX Impact/Octane feedback bug work around.  If the feedback
  1238.      buffer on Impact/Octane is less than 2048 entries, a buggy
  1239.      hardware accelerated path is used.  Make sure at least 2049
  1240.      entries for the feedback buffer; this forces Impact/Octane to use
  1241.      the (bug free) software feedback path.  This bug is fixed in IRIX
  1242.      6.5. */
  1243.   if (object->feedbackBufferSizeGuess < 2048) {
  1244.     object->feedbackBufferSizeGuess = 2048;
  1245.   }
  1246. #endif
  1247.  
  1248.   object->state = RTS_SHADOWING;
  1249.  
  1250.   object->lightListSize = 0;
  1251.   object->lightList = NULL;
  1252.  
  1253.   return object;
  1254. }
  1255.  
  1256. void
  1257. rtsAddLightToScene(
  1258.   RTSscene * scene,
  1259.   RTSlight * light)
  1260. {
  1261.   int i;
  1262.  
  1263.   for (i = 0; i < light->sceneListSize; i++) {
  1264.     if (light->sceneList[i] == scene) {
  1265.       return;
  1266.     }
  1267.     if (light->sceneList[i] == NULL) {
  1268.       goto addToSceneList;
  1269.     }
  1270.   }
  1271.   light->sceneListSize++;
  1272.   light->sceneList = (RTSscene **) SHARED_REALLOC(light->sceneList,
  1273.     light->sceneListSize * sizeof(RTSscene *));
  1274.   if (light->sceneList == NULL) {
  1275.     fprintf(stderr, "rtsAddLightToScene: out of memory\n");
  1276.     abort();
  1277.   }
  1278. addToSceneList:
  1279.  
  1280.   light->sceneList[i] = scene;
  1281.  
  1282.   for (i = 0; i < scene->lightListSize; i++) {
  1283.     if (scene->lightList[i] == light) {
  1284.       fprintf(stderr, "rtsAddLightToScene: inconsistent lists\n");
  1285.       abort();
  1286.     }
  1287.     if (scene->lightList[i] == NULL) {
  1288.       goto addToLightList;
  1289.     }
  1290.   }
  1291.   scene->lightListSize++;
  1292.   scene->lightList = (RTSlight **) SHARED_REALLOC(scene->lightList,
  1293.     scene->lightListSize * sizeof(RTSlight *));
  1294.   if (scene->lightList == NULL) {
  1295.     fprintf(stderr, "rtsAddLightToScene: out of memory\n");
  1296.     abort();
  1297.   }
  1298. addToLightList:
  1299.  
  1300.   scene->lightList[i] = light;
  1301.  
  1302.   light->refcnt++;
  1303. }
  1304.  
  1305. static void
  1306. initShadowVolumeState(ShadowVolumeState * svs)
  1307. {
  1308.   svs->lightSernum = 0;
  1309.   svs->objectSernum = 0;
  1310.   svs->silhouette = NULL;
  1311.   svs->silhouetteSize = 0;
  1312. #ifdef MP
  1313.   svs->generationDone = 0;
  1314. #endif
  1315. }
  1316.  
  1317. void
  1318. rtsAddObjectToLight(
  1319.   RTSlight * light,
  1320.   RTSobject * object)
  1321. {
  1322.   int i;
  1323.  
  1324.   for (i = 0; i < object->lightListSize; i++) {
  1325.     if (object->lightList[i] == light) {
  1326.       return;
  1327.     }
  1328.     if (object->lightList[i] == NULL) {
  1329.       goto addToLightList;
  1330.     }
  1331.   }
  1332.   object->lightListSize++;
  1333.   object->lightList = (RTSlight **) SHARED_REALLOC(object->lightList,
  1334.     object->lightListSize * sizeof(RTSlight *));
  1335.   if (object->lightList == NULL) {
  1336.     fprintf(stderr, "rtsAddObjectToLight: out of memory\n");
  1337.     abort();
  1338.   }
  1339. addToLightList:
  1340.   object->lightList[i] = light;
  1341.  
  1342.   for (i = 0; i < light->objectListSize; i++) {
  1343.     if (light->objectList[i] == object) {
  1344.       fprintf(stderr, "rtsAddObjectToLight: inconsistent lists\n");
  1345.       abort();
  1346.     }
  1347.     if (light->objectList[i] == NULL) {
  1348.       goto addToObjectList;
  1349.     }
  1350.   }
  1351.  
  1352.   /* Extend object list. */
  1353.   light->objectListSize++;
  1354.   light->objectList = (RTSobject **) SHARED_REALLOC(light->objectList,
  1355.     light->objectListSize * sizeof(RTSscene *));
  1356.   if (light->objectList == NULL) {
  1357.     fprintf(stderr, "rtsAddObjectToLight: out of memory\n");
  1358.     abort();
  1359.   }
  1360.   /* Extend shadow volume list. */
  1361.   light->shadowVolumeList = (ShadowVolumeState *)
  1362.     SHARED_REALLOC(light->shadowVolumeList,
  1363.     light->objectListSize * sizeof(ShadowVolumeState));
  1364.   if (light->shadowVolumeList == NULL) {
  1365.     fprintf(stderr, "rtsAddObjectToLight: out of memory\n");
  1366.     abort();
  1367.   }
  1368. addToObjectList:
  1369.  
  1370.   initShadowVolumeState(&light->shadowVolumeList[i]);
  1371.  
  1372.   light->objectList[i] = object;
  1373.  
  1374.   light->refcnt++;
  1375.   object->refcnt++;
  1376. }
  1377.  
  1378. void
  1379. rtsSetLightState(
  1380.   RTSlight * light,
  1381.   RTSlightState state)
  1382. {
  1383.   light->state = state;
  1384. }
  1385.  
  1386. void
  1387. rtsSetObjectState(
  1388.   RTSobject * object,
  1389.   RTSobjectState state)
  1390. {
  1391.   object->state = state;
  1392. }
  1393.  
  1394. void
  1395. rtsUpdateEyePos(
  1396.   RTSscene * scene,
  1397.   GLfloat eyePos[3])
  1398. {
  1399.   scene->eyePos[X] = eyePos[X];
  1400.   scene->eyePos[Y] = eyePos[Y];
  1401.   scene->eyePos[Z] = eyePos[Z];
  1402. }
  1403.  
  1404. void
  1405. rtsUpdateUsableStencilBits(
  1406.   RTSscene * scene,
  1407.   GLbitfield usableStencilBits)
  1408. {
  1409.   scene->usableStencilBits = usableStencilBits;
  1410.   scene->stencilValidateNeeded = 1;
  1411. }
  1412.  
  1413. void
  1414. rtsUpdateLightPos(
  1415.   RTSlight * light,
  1416.   GLfloat lightPos[3])
  1417. {
  1418.   light->lightPos[X] = lightPos[X];
  1419.   light->lightPos[Y] = lightPos[Y];
  1420.   light->lightPos[Z] = lightPos[Z];
  1421.   light->sernum++;
  1422. }
  1423.  
  1424. void
  1425. rtsUpdateLightRadius(
  1426.   RTSlight * light,
  1427.   GLfloat radius)
  1428. {
  1429.   light->radius = radius;
  1430.   light->sernum++;
  1431. }
  1432.  
  1433. void
  1434. rtsUpdateObjectPos(
  1435.   RTSobject * object,
  1436.   GLfloat objectPos[3])
  1437. {
  1438.   object->objectPos[X] = objectPos[X];
  1439.   object->objectPos[Y] = objectPos[Y];
  1440.   object->objectPos[Z] = objectPos[Z];
  1441.   object->sernum++;
  1442. }
  1443.  
  1444. void
  1445. rtsUpdateObjectShape(
  1446.   RTSobject * object)
  1447. {
  1448.   object->sernum++;
  1449. }
  1450.  
  1451. void
  1452. rtsUpdateObjectMaxRadius(
  1453.   RTSobject * object,
  1454.   GLfloat maxRadius)
  1455. {
  1456.   object->maxRadius = maxRadius;
  1457.   object->sernum++;
  1458. }
  1459.  
  1460. #if defined(GL_EXT_vertex_array) && !defined(GL_VERSION_1_1)
  1461. /* Only needed if has vertex array extension, but no OpenGL 1.1. */
  1462. static void
  1463. setupVertexArray(ShadowVolumeState * svs, int numCoordinates)
  1464. {
  1465.   glDisable(GL_EDGE_FLAG_ARRAY_EXT);
  1466.   glEnable(GL_VERTEX_ARRAY_EXT);
  1467.   glDisable(GL_NORMAL_ARRAY_EXT);
  1468.   glDisable(GL_COLOR_ARRAY_EXT);
  1469.   glDisable(GL_TEXTURE_COORD_ARRAY_EXT);
  1470.   glDisable(GL_EDGE_FLAG_ARRAY_EXT);
  1471.   glVertexPointerEXT(numCoordinates, GL_FLOAT, 3 * sizeof(GLfloat), svs->silhouetteSize, svs->silhouette);
  1472. }
  1473. #endif
  1474.  
  1475. static void
  1476. renderSilhouette(ShadowVolumeState * svs)
  1477. {
  1478.   int *infoPtr = (int *) svs->silhouette;
  1479.   int *info = infoPtr;
  1480.   int end, i;
  1481.  
  1482.   /* CONSTANTCONDITION */
  1483.   assert(sizeof(GLfloat) == sizeof(GLint));
  1484.  
  1485.   if (hasVertexArray) {
  1486. #if defined(GL_VERSION_1_1)
  1487.     glInterleavedArrays(GL_V2F, 3 * sizeof(GLfloat), svs->silhouette);
  1488. #elif defined(GL_EXT_vertex_array)
  1489.     setupVertexArray(svs, 2);
  1490. #endif
  1491.   }
  1492.   for (;;) {
  1493.     assert(info[2] == 0xdeadbeef || info[2] == 0xcafecafe);
  1494.     /* Two fewer vertices get rendered in the renderSilhouette case (compared
  1495.        to renderShadowVolumeBase) because because a line loop does not need
  1496.        the initial fan center or the final repeated first vertex. */
  1497.     if (hasVertexArray) {
  1498. #if defined(GL_VERSION_1_1)
  1499.       glDrawArrays(GL_LINE_LOOP, info[0] + 1, info[1] - 2);
  1500. #elif defined(GL_EXT_vertex_array)
  1501.       glDrawArraysEXT(GL_LINE_LOOP, info[0] + 1, info[1] - 2);
  1502. #endif
  1503.     } else {
  1504.       glBegin(GL_LINE_LOOP);
  1505.       end = info[0] + info[1] - 2;
  1506.       for (i = info[0] + 1; i < end; i++) {
  1507.         glVertex2fv(&svs->silhouette[i * 3]);
  1508.       }
  1509.       glEnd();
  1510.     }
  1511.     if (info[2] == 0xcafecafe) {
  1512.       return;
  1513.     }
  1514.     info += ((1 + info[1]) * 3);
  1515.   }
  1516. }
  1517.  
  1518. static void
  1519. renderShadowVolumeBase(ShadowVolumeState * svs)
  1520. {
  1521.   int *infoPtr = (int *) svs->silhouette;
  1522.   int *info = infoPtr;
  1523.   int end, i;
  1524.   int fan;
  1525.  
  1526.   fan = 0;
  1527.   /* CONSTANTCONDITION */
  1528.   assert(sizeof(GLfloat) == sizeof(GLint));
  1529.   glRotatef(svs->angle, svs->axis[X], svs->axis[Y], svs->axis[Z]);
  1530.   for (;;) {
  1531.     assert((info[2] == 0xdeadbeef || info[2] == 0xcafecafe) && info[1] > 0);
  1532.     if (hasVertexArray) {
  1533.       /* Note: assumes that glInterleavedArrays has already been called. */
  1534. #if defined(GL_VERSION_1_1)
  1535.       glDrawArrays(GL_TRIANGLE_FAN, info[0], info[1]);
  1536. #elif defined(GL_EXT_vertex_array)
  1537.       glDrawArraysEXT(GL_TRIANGLE_FAN, info[0], info[1]);
  1538. #endif
  1539.     } else {
  1540.       glBegin(GL_TRIANGLE_FAN);
  1541.       end = info[0] + info[1];
  1542.       for (i = info[0]; i < end; i++) {
  1543.         glVertex3fv(&svs->silhouette[i * 3]);
  1544.       }
  1545.       glEnd();
  1546.     }
  1547.     if (info[2] == 0xcafecafe) {
  1548.       return;
  1549.     }
  1550.     assert(info[1] > 0);
  1551.     info += ((1 + info[1]) * 3);
  1552.     fan++;
  1553.   }
  1554. }
  1555.  
  1556. static void
  1557. renderShadowVolume(ShadowVolumeState * svs, GLfloat lightPos[3])
  1558. {
  1559.   glPushMatrix();
  1560.   glTranslatef(lightPos[X], lightPos[Y], lightPos[Z]);
  1561.   renderShadowVolumeBase(svs);
  1562.   glPopMatrix();
  1563. }
  1564.  
  1565. static void
  1566. renderShadowVolumeTop(ShadowVolumeState * svs, GLfloat lightPos[3])
  1567. {
  1568.   glPushMatrix();
  1569.   glTranslatef(lightPos[X], lightPos[Y], lightPos[Z]);
  1570.   glScalef(svs->topScale, svs->topScale, svs->topScale);
  1571.   renderShadowVolumeBase(svs);
  1572.   glPopMatrix();
  1573. }
  1574.  
  1575. static void
  1576. validateShadowVolume(RTSscene * scene, RTSlight * light,
  1577.   RTSobject * object, ShadowVolumeState * svs)
  1578. {
  1579.   /* Serial number mismatch indicates light or object has changed since last
  1580.      shadow volume generation. If mismatch, regenerate the shadow volume. */
  1581.   if (light->sernum != svs->lightSernum
  1582.     || object->sernum != svs->objectSernum) {
  1583.     TessellationContext *workContext;
  1584. #ifdef MP
  1585.     int i;
  1586.  
  1587.     WAIT(contextAvailable);
  1588.  
  1589.     LOCK(accessQueue);
  1590.     workContext = NULL;
  1591.     for (i=0; i<NUM_CONTEXTS; i++) {
  1592.       if (context[i]->state == CS_UNUSED) {
  1593.         workContext = context[i];
  1594.     break;
  1595.       }
  1596.     }
  1597.     assert(workContext);
  1598.     workContext->state = CS_CAPTURING;
  1599.     UNLOCK(accessQueue);
  1600.  
  1601.     captureLightView(scene, light,
  1602.       object, svs, workContext);
  1603.     
  1604.     workContext->state = CS_QUEUED;
  1605.     SIGNAL(silhouetteNeedsGeneration);
  1606.  
  1607. #else
  1608.     workContext = context[0];
  1609.     captureLightView(scene, light,
  1610.       object, svs, workContext);
  1611.  
  1612.     generateSilhouette(workContext);
  1613. #endif
  1614.   }
  1615. }
  1616.  
  1617. void
  1618. rtsRenderScene(
  1619.   RTSscene * scene,
  1620.   RTSmode mode)
  1621. {
  1622.   static GLfloat totalDarkness[4] =
  1623.   {0.0, 0.0, 0.0, 0.0};
  1624.   int i, obj, bit;
  1625.   int numStencilBits, numCastingLights, numShadowingObjects;
  1626.   RTSlight *firstLight, *prevLight, *light;
  1627.   RTSobject *object;
  1628.   GLbitfield fullStencilMask;
  1629.  
  1630.   /* Expect application (caller) to do the glClear (including stencil). */
  1631.   /* Expect application (caller) to enable depth testing. */
  1632.  
  1633.   if (mode != RTS_NO_SHADOWS) {
  1634.     /* Validate shadow volumes, count casting lights, and stash the first
  1635.        light. */
  1636.     numCastingLights = 0;
  1637.     firstLight = NULL;
  1638.     for (i = 0; i < scene->lightListSize; i++) {
  1639.       light = scene->lightList[i];
  1640.       if (light) {
  1641.         if (light->state != RTS_OFF) {
  1642.           if (light->state == RTS_SHINING_AND_CASTING) {
  1643.  
  1644.             if (numCastingLights == 0) {
  1645.               /* Count number of shadowing objects. */
  1646.               numShadowingObjects = 0;
  1647.               for (obj = 0; obj < light->objectListSize; obj++) {
  1648.                 if (light->objectList[obj]->state == RTS_SHADOWING) {
  1649.                   numShadowingObjects++;
  1650.                 }
  1651.               }
  1652.               if (numShadowingObjects == 0) {
  1653.                 /* Not casting on any object; skip it. */
  1654.                 continue;
  1655.               }
  1656.               assert(firstLight == NULL);
  1657.               firstLight = light;
  1658.             }
  1659.             numCastingLights++;
  1660.             if (numCastingLights == 1 || hasBlendSubtract) {
  1661.               glEnable(light->glLight);
  1662.             } else {
  1663.               glDisable(light->glLight);
  1664.             }
  1665.  
  1666.             for (obj = 0; obj < light->objectListSize; obj++) {
  1667.               object = light->objectList[obj];
  1668.               if (object->state == RTS_SHADOWING) {
  1669.                 ShadowVolumeState *svs;
  1670.  
  1671.                 svs = &light->shadowVolumeList[obj];
  1672.                 validateShadowVolume(scene, light, object, svs);
  1673.               }
  1674.             }
  1675.           } else if (light->state == RTS_SHINING_AND_CASTING) {
  1676.             glEnable(light->glLight);
  1677.           }
  1678.         } else {
  1679.           glDisable(light->glLight);
  1680.         }
  1681.       }
  1682.     }
  1683.   }
  1684.   glEnable(GL_LIGHTING);
  1685.   glEnable(GL_CULL_FACE);
  1686.   if (scene->stencilRenderingInvariantHack) {
  1687.     glEnable(GL_STENCIL_TEST);
  1688.     glStencilFunc(GL_ALWAYS, 0, 0xffffffff);
  1689.     glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
  1690.   } else {
  1691.     /* XXX Note that the non-hack case does not enable or
  1692.        disable stencil.  The hack case enables stencil
  1693.        testing but sets up the stencil modes so that stencil
  1694.        testing is effectively disabled.  If you wanted
  1695.        stencil testing on during the renderSceneFunc, you won't
  1696.        need to have the hack enabled though! */
  1697.   }
  1698.   scene->renderSceneFunc(GL_NONE, scene->sceneData, scene);
  1699.  
  1700.   if (mode == RTS_NO_SHADOWS) {
  1701.     return;
  1702.   }
  1703.   if (numCastingLights == 0) {
  1704.     /* No lights, no shadows. */
  1705.     return;
  1706.   }
  1707.   assert(firstLight);
  1708.   assert(numShadowingObjects > 0);
  1709.  
  1710.   /* Determine exactly which stencil bits usable for shadowing. */
  1711.   if (scene->stencilValidateNeeded) {
  1712.     GLbitfield shadowStencilBits;
  1713.  
  1714.     shadowStencilBits = scene->usableStencilBits & ((1 << scene->stencilBits) - 1);
  1715.     scene->numStencilBits = listBits(shadowStencilBits, scene->bitList);
  1716.     if (scene->numStencilBits == 0) {
  1717.       fprintf(stderr,
  1718.         "WARNING: No stencil bits available for shadowing, expect bad results.\n");
  1719.       fprintf(stderr,
  1720.         "         Frame buffer stencil bits = %d, usable stencil bits = 0x%x.\n",
  1721.         scene->stencilBits, scene->usableStencilBits);
  1722.     }
  1723.     scene->stencilValidateNeeded = 0;
  1724.   }
  1725.   numStencilBits = scene->numStencilBits;
  1726.  
  1727.   /* The first light is easier than the rest since we need subtractive
  1728.      blending for two or more lights. Do the first light the fast way. */
  1729.  
  1730.   bit = 0;
  1731.   assert(scene->stencilValidateNeeded == 0);
  1732.  
  1733.   glDisable(firstLight->glLight);
  1734.   glEnable(GL_STENCIL_TEST);
  1735.   glDepthMask(GL_FALSE);
  1736.  
  1737.   obj = 0;
  1738.   while (firstLight->objectList[obj]->state == RTS_NOT_SHADOWING) {
  1739.     obj++;
  1740.   }
  1741.  
  1742.   do {
  1743.     assert(bit < numStencilBits);
  1744.     assert(firstLight->objectList[obj]->state == RTS_SHADOWING);
  1745.     assert(obj < firstLight->objectListSize);
  1746.  
  1747.     fullStencilMask = 0;
  1748.  
  1749.     glDisable(GL_LIGHTING);
  1750.     glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
  1751.     glDisable(GL_CULL_FACE);
  1752.     glStencilFunc(GL_ALWAYS, 0, 0);
  1753.     do {
  1754.  
  1755. #ifdef MP
  1756.       waitForSilhouetteGenerationDone(scene, &firstLight->shadowVolumeList[obj]);
  1757. #endif
  1758.  
  1759.       if (hasVertexArray) {
  1760. #if defined(GL_VERSION_1_1)
  1761.         glInterleavedArrays(GL_V3F, 0,
  1762.           firstLight->shadowVolumeList[obj].silhouette);
  1763. #elif defined(GL_EXT_vertex_array)
  1764.         setupVertexArray(&firstLight->shadowVolumeList[obj], 3);
  1765. #endif
  1766.       }
  1767.       fullStencilMask |= 1 << scene->bitList[bit];
  1768.       glStencilMask(1 << scene->bitList[bit]);
  1769.       glStencilOp(GL_KEEP, GL_KEEP, GL_INVERT);
  1770.       renderShadowVolume(&firstLight->shadowVolumeList[obj],
  1771.         firstLight->lightPos);
  1772.  
  1773.       glStencilOp(GL_KEEP, GL_KEEP, GL_ZERO);
  1774.       renderShadowVolumeTop(&firstLight->shadowVolumeList[obj],
  1775.         firstLight->lightPos);
  1776.  
  1777.       bit++;
  1778.       do {
  1779.         obj++;
  1780.       } while (obj < firstLight->objectListSize
  1781.         && firstLight->objectList[obj]->state == RTS_NOT_SHADOWING);
  1782.  
  1783.     } while (bit < numStencilBits && obj < firstLight->objectListSize);
  1784.  
  1785.     glEnable(GL_CULL_FACE);
  1786.     glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
  1787.     glDepthFunc(GL_EQUAL);
  1788.     glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
  1789.     glStencilFunc(GL_NOTEQUAL, 0, fullStencilMask);
  1790.     glEnable(GL_LIGHTING);
  1791.     scene->renderSceneFunc(firstLight->glLight, scene->sceneData, scene);
  1792.     if (obj < firstLight->objectListSize) {
  1793.       glStencilMask(~0);
  1794.       glClear(GL_STENCIL_BUFFER_BIT);
  1795.       glDepthFunc(GL_LESS);  /* XXX needed? */
  1796.       bit = 0;
  1797.     }
  1798.   } while (obj < firstLight->objectListSize);
  1799.  
  1800.   if (numCastingLights == 1) {
  1801.     glStencilMask(~0);
  1802.     glCullFace(GL_BACK);  /* XXX Needed? */
  1803.     glDepthMask(GL_TRUE);
  1804.     glDepthFunc(GL_LESS);
  1805.     if (scene->stencilRenderingInvariantHack) {
  1806.       glEnable(GL_STENCIL_TEST);
  1807.       glStencilFunc(GL_ALWAYS, 0, 0xffffffff);
  1808.       glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
  1809.     } else {
  1810.       glDisable(GL_STENCIL_TEST);
  1811.     }
  1812.     if (hasVertexArray) {
  1813. #if defined(GL_VERSION_1_1)
  1814.       glDisableClientState(GL_VERTEX_ARRAY);
  1815. #elif defined(GL_EXT_vertex_array)
  1816.       glDisable(GL_VERTEX_ARRAY_EXT);
  1817. #endif
  1818.     }
  1819.     return;
  1820.   }
  1821.   /* Get ready to subtract out the particular contribution for each light
  1822.      source in regions shadowed by the light source's shadowing objects. */
  1823.   glLightModelfv(GL_LIGHT_MODEL_AMBIENT, totalDarkness);
  1824.   glDepthFunc(GL_LESS);
  1825. #ifdef GL_EXT_blend_subtract
  1826.   if (hasBlendSubtract) {
  1827.     glBlendEquationEXT(GL_FUNC_REVERSE_SUBTRACT_EXT);
  1828.   }
  1829. #endif
  1830.   glBlendFunc(GL_ONE, GL_ONE);
  1831.   glEnable(GL_BLEND);
  1832.  
  1833.   prevLight = firstLight;
  1834.  
  1835.   for (i = 1; i < scene->lightListSize; i++) {
  1836.     light = scene->lightList[i];
  1837.     if (light) {
  1838.       if (light->state == RTS_SHINING_AND_CASTING) {
  1839.  
  1840.         /* Count number of shadowing objects. */
  1841.         numShadowingObjects = 0;
  1842.         for (obj = 0; obj < light->objectListSize; obj++) {
  1843.           if (light->objectList[obj]->state == RTS_SHADOWING) {
  1844.             numShadowingObjects++;
  1845.           }
  1846.         }
  1847.  
  1848.         if (numShadowingObjects > 0) {
  1849.           int reservedStencilBit;
  1850.  
  1851.           assert(scene->stencilValidateNeeded == 0);
  1852.  
  1853.           /* Switch off the last light; switch on the current light (all
  1854.              other lights should be disabled). */
  1855.           glDisable(prevLight->glLight);
  1856.           glEnable(light->glLight);
  1857.  
  1858.           /* Complicated logic to try to figure out the stencil clear
  1859.              strategy.  Tries hard to conserve stencil bit planes and scene
  1860.              re-renders. */
  1861.           if (numStencilBits < numShadowingObjects) {
  1862.             if (numStencilBits == 1) {
  1863.               fprintf(stderr, "WARNING: 1 bit of stencil not enough to reserve a bit.\n");
  1864.               fprintf(stderr, "         Skipping lights beyond the first.\n");
  1865.               continue;
  1866.             }
  1867.             /* Going to require one or more stencil clears; this requires
  1868.                reserving a bit of stencil to avoid double subtracts. */
  1869.             reservedStencilBit = 1 << scene->bitList[0];
  1870.             bit = 1;
  1871.             glStencilMask(~0);
  1872.             glClear(GL_STENCIL_BUFFER_BIT);
  1873.             glDepthFunc(GL_LESS);  /* XXX Needed? */
  1874.           } else {
  1875.             /* Faster cases.  All the objects can be rendered each to a
  1876.                distinct available stencil plane.  No need to reserve a
  1877.                stencil bit to avoid double blending since only one scene
  1878.                render required. */
  1879.             reservedStencilBit = 0;
  1880.             if (numShadowingObjects <= numStencilBits - bit) {
  1881.               /* Best case:  Enough stencil bits available to not even
  1882.                  require a stencil clear for this light.  Keep "bit" as is. */
  1883.             } else {
  1884.               /* Not enough left over bitplanes to subtract out this light
  1885.                  with what's currently available, so clear the stencil buffer
  1886.                  to get enough. */
  1887.               glStencilMask(~0);
  1888.               glClear(GL_STENCIL_BUFFER_BIT);
  1889.               bit = 0;
  1890.             }
  1891.           }
  1892.  
  1893.           obj = 0;
  1894.           while (light->objectList[obj]->state == RTS_NOT_SHADOWING) {
  1895.             obj++;
  1896.           }
  1897.  
  1898.           do {
  1899.             assert(bit < numStencilBits);
  1900.             assert(light->objectList[obj]->state == RTS_SHADOWING);
  1901.             assert(obj < light->objectListSize);
  1902.  
  1903.             fullStencilMask = reservedStencilBit;
  1904.  
  1905.             glDisable(GL_LIGHTING);
  1906.             glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
  1907.             glStencilFunc(GL_ALWAYS, 0, 0);
  1908.             glDisable(GL_CULL_FACE);
  1909.             do {
  1910.  
  1911. #ifdef MP
  1912.               waitForSilhouetteGenerationDone(scene,
  1913.             &light->shadowVolumeList[obj]);
  1914. #endif
  1915.  
  1916.               if (hasVertexArray) {
  1917. #if defined(GL_VERSION_1_1)
  1918.                 glInterleavedArrays(GL_V3F, 0,
  1919.                   light->shadowVolumeList[obj].silhouette);
  1920. #elif defined(GL_EXT_vertex_array)
  1921.                 setupVertexArray(&light->shadowVolumeList[obj], 3);
  1922. #endif
  1923.               }
  1924.               fullStencilMask |= 1 << scene->bitList[bit];
  1925.               glStencilMask(1 << scene->bitList[bit]);
  1926.               glStencilOp(GL_KEEP, GL_KEEP, GL_INVERT);
  1927.               renderShadowVolume(&light->shadowVolumeList[obj],
  1928.                 light->lightPos);
  1929.  
  1930.               glStencilOp(GL_KEEP, GL_KEEP, GL_ZERO);
  1931.               renderShadowVolumeTop(&light->shadowVolumeList[obj],
  1932.                 light->lightPos);
  1933.  
  1934.               bit++;
  1935.               do {
  1936.                 obj++;
  1937.               } while (obj < light->objectListSize
  1938.                 && light->objectList[obj]->state == RTS_NOT_SHADOWING);
  1939.  
  1940.             } while (bit < scene->numStencilBits && obj < light->objectListSize);
  1941.  
  1942.             glEnable(GL_CULL_FACE);
  1943.             glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
  1944.             glDepthFunc(GL_EQUAL);
  1945.             if (reservedStencilBit) {
  1946.               glStencilMask(reservedStencilBit);
  1947.               glStencilOp(GL_KEEP, GL_KEEP, GL_ONE);
  1948.               if (hasBlendSubtract) {
  1949.                 /* Subtract lighting contribution inside of shadow; prevent
  1950.                    double drawing via stencil */
  1951.                 glStencilFunc(GL_GREATER, reservedStencilBit, fullStencilMask);
  1952.               } else {
  1953.                 /* Add lighting contribution outside of shadow; prevent
  1954.                    double drawing via stencil. */
  1955.                 glStencilFunc(GL_EQUAL, 0, fullStencilMask);
  1956.               }
  1957.             } else {
  1958.               if (hasBlendSubtract) {
  1959.                 glStencilOp(GL_KEEP, GL_KEEP, GL_ZERO);
  1960.                 glStencilFunc(GL_NOTEQUAL, 0, fullStencilMask);
  1961.               } else {
  1962.                 glStencilOp(GL_KEEP, GL_KEEP, GL_REPLACE);
  1963.                 glStencilFunc(GL_EQUAL, 0, fullStencilMask);
  1964.               }
  1965.             }
  1966.             glEnable(GL_LIGHTING);
  1967.             scene->renderSceneFunc(light->glLight, scene->sceneData, scene);
  1968.  
  1969.             if (obj < light->objectListSize) {
  1970.               assert(reservedStencilBit);
  1971.               glStencilMask(~0);
  1972.               glClear(GL_STENCIL_BUFFER_BIT);
  1973.               glDepthFunc(GL_LESS);  /* XXX Needed? */
  1974.               bit = 1;
  1975.             }
  1976.           } while (obj < light->objectListSize);
  1977.  
  1978.           prevLight = light;
  1979.         }
  1980.       }
  1981.     }
  1982.   }
  1983.  
  1984.   glStencilMask(~0);
  1985.   glCullFace(GL_BACK);  /* XXX needed? */
  1986.   glDepthMask(GL_TRUE);
  1987.   glDepthFunc(GL_LESS);
  1988.   if (scene->stencilRenderingInvariantHack) {
  1989.     glEnable(GL_STENCIL_TEST);
  1990.     glStencilFunc(GL_ALWAYS, 0, 0xffffffff);
  1991.     glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
  1992.   } else {
  1993.     glDisable(GL_STENCIL_TEST);
  1994.   }
  1995.   glDisable(GL_BLEND);
  1996.   if (hasVertexArray) {
  1997. #if defined(GL_VERSION_1_1)
  1998.     glDisableClientState(GL_VERTEX_ARRAY);
  1999. #elif defined(GL_EXT_vertex_array)
  2000.     glDisable(GL_VERTEX_ARRAY_EXT);
  2001. #endif
  2002.   }
  2003.   glLightModelfv(GL_LIGHT_MODEL_AMBIENT, scene->sceneAmbient);
  2004. }
  2005.  
  2006. void
  2007. rtsRenderSilhouette(
  2008.   RTSscene * scene,
  2009.   RTSlight * light,
  2010.   RTSobject * object)
  2011. {
  2012.   GLfloat lightDelta[3];
  2013.   GLfloat lightDistance, viewScale, fieldOfViewRatio, extentScale;
  2014.   ShadowVolumeState svsRec, *svs;
  2015.   int obj;
  2016.   int anonymousShadowVolumeState;
  2017.  
  2018.   /* Calculate the light's distance from the object being shadowed. */
  2019.   lightDelta[X] = object->objectPos[X] - light->lightPos[X];
  2020.   lightDelta[Y] = object->objectPos[Y] - light->lightPos[Y];
  2021.   lightDelta[Z] = object->objectPos[Z] - light->lightPos[Z];
  2022.   lightDistance = sqrt(lightDelta[X] * lightDelta[X] +
  2023.     lightDelta[Y] * lightDelta[Y] + lightDelta[Z] * lightDelta[Z]);
  2024.  
  2025.   viewScale = getViewScale(scene);
  2026.   fieldOfViewRatio = object->maxRadius / lightDistance;
  2027.   extentScale = light->radius * fieldOfViewRatio / viewScale;
  2028.  
  2029.   for (obj = 0; obj < light->objectListSize; obj++) {
  2030.     if (light->objectList[obj] == object) {
  2031.       svs = &light->shadowVolumeList[obj];
  2032.       anonymousShadowVolumeState = 0;
  2033.       goto gotShadowVolumeState;
  2034.     }
  2035.   }
  2036.  
  2037.   /* It probably makes sense to have the object on the light's object list
  2038.      already since then we would have a ShadowVolumeState structure ready to
  2039.      use and likely to have a reasonably sized silhouette vertex array. Plus,
  2040.      we'd validate the light and object's shadow volume.
  2041.  
  2042.      Anyway, rtsRenderSilhouette will still handle the case where the object
  2043.      is not already added to the specified light for generality (but not
  2044.      economy).  Use an "anonymous" ShadowVolumeState data structure that only
  2045.      lives during this routine. */
  2046.  
  2047.   svs = &svsRec;
  2048.   anonymousShadowVolumeState = 1;
  2049.   initShadowVolumeState(svs);
  2050.  
  2051. gotShadowVolumeState:
  2052.  
  2053.   validateShadowVolume(scene, light, object, svs);
  2054.  
  2055.   glPushAttrib(GL_ENABLE_BIT);
  2056.   /* Disable a few things likely to screw up the rendering of  the
  2057.      silhouette. */
  2058.   glDisable(GL_LIGHTING);
  2059.   glDisable(GL_DEPTH_TEST);
  2060. #if 0
  2061.   glDisable(GL_STENCIL_TEST);
  2062. #else
  2063.   glEnable(GL_STENCIL_TEST);
  2064.   glStencilFunc(GL_ALWAYS, 0, 0xffffffff);
  2065.   glStencilOp(GL_KEEP, GL_KEEP, GL_KEEP);
  2066. #endif
  2067.   glDisable(GL_ALPHA_TEST);
  2068.   glDisable(GL_BLEND);
  2069.  
  2070.   glMatrixMode(GL_PROJECTION);
  2071.   glPushMatrix();
  2072.   glLoadIdentity();
  2073.   gluOrtho2D(-viewScale, viewScale, -viewScale, viewScale);
  2074.   glMatrixMode(GL_MODELVIEW);
  2075.   glPushMatrix();
  2076.   glLoadIdentity();
  2077.   glScalef(1.0 / extentScale, 1.0 / extentScale, 1.0 / extentScale);
  2078.  
  2079.   renderSilhouette(svs);
  2080.  
  2081. #if 0
  2082.   glColor3f(0.0, 1.0, 0.0);
  2083.   glPointSize(7.0);
  2084.   glBegin(GL_POINTS);
  2085.   glVertex2fv(eyeLoc);
  2086.   glEnd();
  2087. #endif
  2088.  
  2089.   glMatrixMode(GL_PROJECTION);
  2090.   glPopMatrix();
  2091.   glMatrixMode(GL_MODELVIEW);
  2092.   glPopMatrix();
  2093.   glPopAttrib();
  2094.  
  2095.   if (anonymousShadowVolumeState) {
  2096.     /* Deallocate "anonymous" ShadowVolumeState's silhouette vertex array. */
  2097.     SHARED_FREE(svs->silhouette);
  2098.   }
  2099. }
  2100.  
  2101. void
  2102. rtsStencilRenderingInvariantHack(RTSscene * scene, GLboolean enableHack)
  2103. {
  2104.   scene->stencilRenderingInvariantHack = enableHack;
  2105. }
  2106.  
  2107. /* XXX These free routines are not complete. */
  2108.  
  2109. #if 0
  2110. static void
  2111. freeTessellationContext(TessellationContext *context)
  2112. {
  2113.   gluDeleteTess(context->tess);
  2114.   free(context->feedbackBuffer);
  2115.   free(context);
  2116. }
  2117. #endif
  2118.  
  2119. void
  2120. rtsFreeScene(
  2121.   RTSscene * scene)
  2122. {
  2123.   int i;
  2124.  
  2125.   for (i=0; i < scene->lightListSize; i++) {
  2126.     if (scene->lightList[i]) {
  2127.       rtsFreeLight(scene->lightList[i]);
  2128.     }
  2129.   }
  2130.   free(scene->lightList);
  2131.   free(scene);
  2132. }
  2133.  
  2134. void
  2135. rtsFreeLight(
  2136.   RTSlight * light)
  2137. {
  2138.   int i;
  2139.  
  2140.   for (i=0; i<light->sceneListSize; i++) {
  2141.     if (light->sceneList[i]) {
  2142.       rtsFreeScene(light->sceneList[i]);
  2143.     }
  2144.   }
  2145.   free(light);
  2146. }
  2147.  
  2148. void
  2149. rtsFreeObject(
  2150.   RTSobject * object)
  2151. {
  2152.   free(object);
  2153. }
  2154.  
  2155. #endif /* GLU_VERSION_1_2 */
  2156.